[프로그래머스] LV.3 풍선 터트리기 (JS)

문제출처

정답 코드

function solution(a) {
  const len = a.length
  const left = new Array(len)
  const right = new Array(len)

  left[0] = a[0]
  right[len - 1] = a[len - 1]

  for (let i = 1; i < len; i++) {
    left[i] = Math.min(left[i - 1], a[i])
  }
  for (let i = len - 2; i >= 0; i--) {
    right[i] = Math.min(right[i + 1], a[i])
  }

  return new Set([...left, ...right]).size
}

해결방법

문제의 조건을 살펴보면

제한 사항

• a의 길이는 1 이상 1,000,000 이하입니다.
  …

a의 max 값이 1,000,000이다.
따라서 시간복잡도를 고려할때 O(N^2)은 사용할 수 없다.

또한 다음과 같은 조건이 주어진다.

• 하지만 인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 할 수 있습니다.

문제를 정리해보면 더 큰 풍선은 마음대로 터트릴 수 있지만, 작은 풍선은 1번만 터트릴 수 있다.

만약 풍선의 전체 구간에서 특정 인덱스를 기준으로 양방향으로 나누고 모두 터트린다면, 왼쪽과 오른쪽에서 최솟값 만 남는다는 의미이다.

특정 인덱스를 기준으로 해서 마지막으로 남은 2개의 값을 비교하면 번호가 더 작은 풍선을 1번은 터트릴 수 있으니깐 둘다 최후의 생존이 가능하다.

우리는 각각 left, right 라는 이름을 가지는 배열을 생성한다.
각 배열에는 해당 인덱스에서 각 방향을 기준으로 가지는 최솟값 을 저장한다.

left, right 배열의 모든 값은 따라서 최후의 생존후보가 된다. 중복을 제거하고 해당 후보 수가 최종값이 된다.

프로그래머스